public class PrimeNumber {


//    统计素数个数
    public static void main(String[] args) {
        System.out.print("暴力算法:");
        System.out.println(bf(100));
        System.out.print("埃氏筛选:");
        System.out.println(isPrime2(100));
    }

//    BF 算法
    public static int bf(int n) {
        int count = 0;
        for (int i = 0; i < n; i++) {
            count += isPrime(i)? 1 : 0;
        }
        return count;
    }
//    判断是否为素数
    public static boolean isPrime(int n) {
        if (n == 0 || n == 1) {
            return false;
        }
        for (int i = 2; i*i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }






//    埃氏筛选
    public static int isPrime2 (int n) {
        int count = 0;
        boolean[] nPrime = new boolean[n];//false代表素数

        for (int i = 2; i < n; i++) { //优化 减少多余计算
            if (!nPrime[i]) {
                count++;
//                for (int j = 2*i; j <= n; j+=i) {
                for (int j = i*i; j < n; j+=i) { //优化 减少多余计算
                    nPrime[j] = true;
                }
            }
        }
        return count;
    }
}
